package demo1;

public class DynamicPlanningPractise {

    public boolean checkPartitioning(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        boolean[][] dp = new boolean[n][n];
        //2 初始化 -无需初始化
        //3 填表
        for(int i = n-1; i >= 0; i--)
            for(int j = i; j < n; j++)
                if(chars[i]==chars[j])
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;
        //4 返回值
        for(int i = 0; i < n-2; i++)
            for(int j = i+1; j < n-1; j++)
                if(dp[0][i] && dp[i+1][j] && dp[j+1][n-1])
                    return true;
        return false;
    }
    public int minCutTest(String s) {
        /**
         解题思想：
         将所有回文子串存储到二维dp表中 */
        //预处理 将所有回文子串保存在dp表中
        char[] chars = s.toCharArray();
        int n = chars.length;
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1; i >= 0; i--)
            for(int j = i+1; j < n; j++)
                if(chars[i]==chars[j])
                    dp[i][j] = i+1<j ? dp[i+1][j-1] : true;

        /**
         状态表示：
         dpp[i]表示以i下标元素为结尾的最长子串（[0，i]子串）所需的最少分割次数  */
        //1 创建dp表
        return 0;
    }

    /**
     * 分割回文串Ⅱ
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int minCut(String s) {
        //预处理
        char[] chars = s.toCharArray();
        int n = chars.length;
        boolean[][] isPal = new boolean[n][n];
        for(int i = n-1; i >= 0; i--)
            for(int j = i; j < n; j++)
                if(chars[i]==chars[j])
                    isPal[i][j] = i+1<j ? isPal[i+1][j-1] : true;
        //1 创建dp表
        int[] dp = new int[n];
        //2 初始化
        for(int i = 0; i < n; i++)
            dp[i] = i;
        //3 填表
        for(int i = 1; i < n; i++){
            if(isPal[0][i]) {
                //若是[0,i]为回文串，则最低分割次数为0
                dp[i] = 0;
                continue;
            }
            /**j==i时，即是表示将最后一个字符分割 */
            for(int j = 1; j <= i; j++) {
                dp[i] = isPal[j][i] ? Math.min(dp[j-1]+1,dp[i]) : dp[i];
            }
        }
        //4 返回值
        return dp[n-1];
    }

    /**
     * 最长回文子序列
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int longestPalindromeSubseq(String s) {
        /**
         状态表示：
         当我们使用经验去定义状态表示时，因为只能表示长度而无法得知具体子序列，
         故无法通过前面的状态去推导后面的状态
         此时我们可以使用范围来定义状态表示，如下：
         dp[i][j] 表示以i下标元素为开始，j下标元素为结尾的 这个区间中最长回文子序列的长度
         为了保证区间有效，故i<=j
         状态转移方程：
         由上述状态表示我们可以尝试去推导状态转移方程，如下：
         当对dp[i][j]填表时，此时有两种情况，如下：
         情况一：chars[i]==chars[j]，可再划分三种
         1：i==j，此时dp[i][j]=1
         2:i+1==j,此时dp[i][j]=2
         3:i+1<j,说明i，j之间相隔元素大于等于一，
         此时dp[i][j]=dp[i+1][j-1]+2 -->因为chars[i]==chars[j]，
         所以我们仅需找到中间区域的最长回文子序列再在两边加上两个相同字符，此时依旧还是回文子序列
         情况二：chars[i]!=chars[j],此时状态转移方程为：
         max(dp[i][j-1],dp[i+1][j]);
         初始化：
         在情况一中，存在dp[i+1][j-1],此时j可能会越界访问，
         由于我们限定i<=j，故我们填表的范围仅在dp表的上半部分，此时可能越界的地方便是dp[0][0]与dp[n-1][n-1]
         但是在情况一中 我们已经对该情况进行特判，当i==j时，dp[i][j]=1,故不存在越界

         在情况二中，存在dp[i][j-1],dp[i+1][j]，此时可能越界的地方便是dp[0][0]与dp[n-1][n-1]
         由于i==j，故chars[i]==chars[j]，且因为i==j，故其一定为1，此种情况在情况一时已处理，故无需初始化
         填表顺序：
         由于在对dp[i][j]填表时其依赖于下、左、左下这三个位置的值，故我们的填表顺序为：
         从下到上，从左到右
         */

        char[] chars = s.toCharArray();
        int n = chars.length;
        //1 创建dp表
        int[][] dp = new int[n][n];
        //2 初始化-无需初始化
        //3 填表
        for(int i = n-1; i >= 0; i--)
            for(int j = i; j < n; j++)
                if(chars[i]==chars[j])
                    dp[i][j] = i+1<j ? dp[i+1][j-1]+2 : i==j ? 1 : 2;
                else
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
        //4 返回值
        return dp[0][n-1];
    }
}
